1. Field of the Invention
This invention is related to the field of integrated circuits and, more particularly, to a rotating pointer buffer often included in integrated circuits.
2. Description of the Related Art
Integrated circuits of various types use buffers to store values in an ordered fashion. The order of the values is typically the order in which the values are stored into the buffer over time. For example, a first-in, first-out (FIFO) buffer orders values as they are stored into the FIFO buffer. Values are removed from the FIFO buffer in the same order in which they were stored in the buffer. FIFO buffers may be used in a modified fashion in which values may be removed from within the buffer (instead of only the oldest value, which is at the "bottom" of the buffer), but generally older values (values which were stored in the buffer earlier in time than other values within the buffer) are favored for selection over newer values (values which were stored in the buffer later in time than other values within the buffer).
FIFO buffers may have many different uses in integrated circuits (such as microprocessors). For example, a microprocessor may implement a reorder buffer as a FIFO buffer. A load/store buffer or a reservation station may be a FIFO type buffer in which values may be removed from entries within the buffer as well as from the "bottom" entry (i.e. the entry storing the oldest value). Generally, a buffer includes multiple entries of equal size. Each of the entries is configured to store a value.
FIFO buffers may physically be implemented in a number of ways. Two often used implementations are the shifting structure and the rotating pointer buffer. In the shifting structure, one entry within the buffer is permanently assigned to be the "bottom" entry in the buffer. A value being stored into the buffer is stored into the entry which is nearest the bottom entry and which is currently empty. As values are removed from the bottom entry in the buffer, values stored in other entries within the buffer are shifted down such that the bottom entry is filled with the oldest remaining value and other entries nearest the bottom are filled with the remaining values.
Alternatively, the rotating pointer buffer does not shift values from entry to entry. A value stored into a particular entry in the rotating pointer buffer remains in the particular lo entry until the value is removed from the buffer. A head pointer is used to indicate the "bottom" entry, and a tail pointer is used to indicate the entry into which new values are to be stored. Deleting a value from the buffer is accomplished by modifying the head pointer, and adding a value to the buffer is accomplished by storing the value into the entry indicated by the tail pointer and modifying the tail pointer. Rotating pointer buffers may also be referred to as "circular buffers".
Table 1 below lists various attributes of rotating pointer buffers and shifting structures, as well as an indication of which implementation is superior with regard to each attribute. The number of entries in the buffer is N.
TABLE 1 ______________________________________ Comparison of Rotating Pointer Buffer to Shifting Structure Rotating Pointer Shifting Structure Superior ______________________________________ Area Latch Flip Flop and Mux Rotating Pointer Input Value Direct Extra Mux Input Rotating Pointer Write (Tail Pointer) Bottom Read N:1 Mux Direct Shifting Structure Any Entry N:1 Mux N:1 Mux equal Read Scan First 2 * N entry scan N entry scan Shifting Structure Hit Next Cycle Direct Extra Mux Input Rotating Pointer R/W (Tail Pointer) Unique Direct Direct equal Entry Hit ______________________________________
As Table 1 illustrates, the rotating pointer structure is superior to or equal to the shifting structure (in terms of complexity, lowest area consumption, and speed) in each of the attributes except for the bottom entry read and the scan for the first hit. The bottom entry read may often times by a non-critical path (i.e. it may be slow without affecting clock cycle time). However, the scan for the first hit (in which a search value is being searched for in the buffer and a particular one of multiple possible matches, or hits, is desired) is more complex and slower in the rotating pointer buffer than in the shifting structure. In the shifting structure, a scan of the N entries is performed (since the order of the entries is based upon physical position in the buffer). In the rotating pointer buffer, effectively two scans of the N entries are performed. One of the scans masks results from the entries between a start pointer indicating where the scan is to be initiated and one end of the buffer, and the other of the scans masks results from the entries between the start pointer and the other end of the buffer. These two scans are then merged to produce a scan result.
Many approaches to scanning for the first hit lead to a large fanout and heavy loading on various signals within the scanning circuitry. Generally, each possible hit is qualified with the lack of any previous hits, masked according to the entry at which searching is initiated. An efficient method for scanning for the first hit in a rotating pointer buffer is therefore desired, to improve the advantages of the rotating pointer buffer implementation over that of the shifting structure.